翻訳と辞書 Words near each other ・ Localizer performance with vertical guidance ・ Localizer type directional aid ・ Localizing subcategory ・ LocalLabs ・ Locallife ・ Locally acyclic morphism ・ Locally catenative sequence ・ Locally compact field ・ Locally compact group ・ Locally compact quantum group ・ Locally compact space ・ Locally connected space ・ Locally constant function ・ Locally convex topological vector space ・ Locally cyclic group ・ Locally decodable code ・ Locally discrete collection ・ Locally finite ・ Locally finite collection ・ Locally finite group ・ Locally finite measure ・ Locally finite operator ・ Locally finite poset ・ Locally finite space ・ Locally finite variety ・ Locally Hausdorff space ・ Locally integrable function ・ Locally listed buildings in Crawley ・ Locally nilpotent ・ Locally normal space Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Locally decodable code ： ウィキペディア英語版 Locally decodable code A locally decodable code (LDC) is an error-correcting code that allows a single bit of the original message to be decoded with high probability by only examining (or querying) a small number of bits of a possibly corrupted codeword. 〔(【引用サイトリンク】format=PDF )〕〔(【引用サイトリンク】format=PDF )〕〔Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, (Technical Report ECCC TR06-127 ), 2006.〕 This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Note that locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two.〔(【引用サイトリンク】title=Locally Testable vs. Locally Decodable Codes )〕 Codewords are generated from the original message using an algorithm that introduces a certain amount of redundancy into the codeword; thus, the codeword is always longer than the original message. This redundancy is distributed across the codeword and allows the original message to be recovered with good probability even in the presence of errors. The more redundant the codeword, the more resilient it is against errors, and the fewer queries required to recover a bit of the original message. == Overview == More formally, a $(q,\; \backslash delta,\; \backslash epsilon)$-locally decodable code encodes an $n$-bit message $x$ to an $N$-bit codeword $C(x)$ such that any bit $x\_i$ of the message can be recovered with probability $1\; -\; \backslash epsilon$ by using a randomized decoding algorithm that queries only $q$ bits of the codeword $C(x)$, even if up to $\backslash delta\; N$ locations of the codeword have been corrupted. Furthermore, a perfectly smooth local decoder is a decoder such that, in addition to always generating the correct output given access to an uncorrupted codeword, for every $j\; \backslash in\; ()$ and $i\; \backslash in\; ()$ the $j^$ query to recover the $i^$ bit is uniform over $()$.〔(【引用サイトリンク】format=PDF )〕 (The notation $()$ denotes the set $\backslash$). Informally, this means that the set of queries required to decode any given bit are uniformly distributed over the codeword. Local list decoders are another interesting subset of local decoders. List decoding is useful when a codeword is corrupted in more than $\backslash delta/2$ places, where $\backslash delta$ is the minimum Hamming distance between two codewords. In this case, it is no longer possible to identify exactly which original message has been encoded, since there could be multiple codewords within $\backslash delta$ distance of the corrupted codeword. However, given a radius $\backslash epsilon$, it is possible to identify the set of messages that encode to codewords that are within $\backslash epsilon$ of the corrupted codeword. An upper bound on the size of the set of messages can be determined by $\backslash delta$ and $\backslash epsilon$. Locally decodable codes can also be concatenated, where a message is encoded first using one scheme, and the resulting codeword is encoded again using a different scheme. (Note that, in this context, concatenation is the term used by scholars to refer to what is usually called composition; see 〔). This might be useful if, for example, the first code has some desirable properties with respect to rate, but it has some undesirable property, such as producing a codeword over a non-binary alphabet. The second code can then transform the result of the first encoding over a non-binary alphabet to a binary alphabet. The final encoding is still locally decodable, and requires additional steps to decode both layers of encoding.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Locally decodable code」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.